//给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。 
//
// 如果数组中不存在目标值 target，返回 [-1, -1]。 
//
// 进阶： 
//
// 
// 你可以设计并实现时间复杂度为 O(log n) 的算法解决此问题吗？ 
// 
//
// 
//
// 示例 1： 
//
// 
//输入：nums = [5,7,7,8,8,10], target = 8
//输出：[3,4] 
//
// 示例 2： 
//
// 
//输入：nums = [5,7,7,8,8,10], target = 6
//输出：[-1,-1] 
//
// 示例 3： 
//
// 
//输入：nums = [], target = 0
//输出：[-1,-1] 
//
// 
//
// 提示： 
//
// 
// 0 <= nums.length <= 105 
// -109 <= nums[i] <= 109 
// nums 是一个非递减数组 
// -109 <= target <= 109 
// 
// Related Topics 数组 二分查找 
// 👍 1735 👎 0


package com.cjl.leetcode.editor.cn;

/**
 * [P34]_在排序数组中查找元素的第一个和最后一个位置
 * @author cjl
 * @date 2022-06-04 13:33:46
 */
public class P34_FindFirstAndLastPositionOfElementInSortedArray{
      public static void main(String[] args) {
            //测试代码
           Solution solution = new P34_FindFirstAndLastPositionOfElementInSortedArray().new Solution();
           int[] res = solution.searchRange(new int[]{1}, 1);
          System.out.println("args = " + res[0] + "," + res[1]);
      }
      //力扣代码
      //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int[] searchRange(int[] nums, int target) {
        if(nums.length == 0){
            return new int[]{-1, -1};
        }
        int start = firstMiddle(nums, target);
        if(start == -1){
            return new int[]{-1, -1};
        }
        int end = lastMiddle(nums, target);
        return new int[]{start,end};
    }

          /**
           * 实现思路：二分法，找最小的 i使得 nums[i] == target; 找最小的j使得nums[j]>target;
           * @param nums
           * @param target
           * @return
           */
    public int firstMiddle(int[] nums, int target){
        int left = 0;
        int right = nums.length-1;
        while (left < right){
            int mid =  (left+right) /2;
            if(nums[mid] > target){
               right = mid -1;
            }else if( nums[mid] == target){
               right = mid;
            }else{
                left = mid +1;
            }
        }
        if(nums[left] == target){
            return left;
        }else {
            return -1;
        }
    }

          public int lastMiddle(int[] nums, int target){
              int left = 0;
              int right = nums.length-1;
              while (left < right){
                  /**
                   * 注意：如果 mid=  (left+right) /2, left=4,right =5,则mid=4；如果此时nums[mid]=target，则left和right不变，陷入死循环；
                   */
                  int mid =  (left+right +1 ) /2;
                  if(nums[mid] > target){
                     right = mid -1;
                  }else if ( nums[mid] == target){
                      left = mid;
                  }else {
                      left = mid +1;
                  }
              }
              if(nums[left] == target){
                  return left;
              }else {
                  return -1;
              }
          }
}
//leetcode submit region end(Prohibit modification and deletion)

  }